package main

/*
硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。
(结果可能会很大，你需要将结果模上1000000007)
*/

import "fmt"

var coins = []int{25, 10, 5, 1}

func waysToChange(n int) int {
	var res int
	var s []int
	change(n, &res, s)
	return res
}

func change(n int, cnt *int, s []int) {
	// 这样的结果无法去重相同的组合情况，是一个排列结果，不是组合结果
	if n == 0 {
		(*cnt)++
		fmt.Println(s)
		return
	} else if n < 0 {
		return
	}
	for _, coin := range coins {
		change(n-coin, cnt, append(s, coin))
	}
}

func waysToChange2(target int) int {
	var dp [][]int
	// dp数组
	for i := 0; i < len(coins)+1; i++ {
		dp = append(dp, make([]int, target+1))
	}
	// base case
	for i := 0; i < len(dp); i++ {
		dp[i][0] = 1
	}
	//状态转移
	for i := 1; i < len(dp); i++ {
		for j := 1; j < len(dp[i]); j++ {
			coinIdx := i - 1
			if j < coins[coinIdx] {
				dp[i][j] = dp[i-1][j]
				continue
			}
			// 如果使用这枚硬币
			useThisCoin := dp[i][j-coins[coinIdx]]
			// 如果不使用这枚硬币
			notUseThisCoin := dp[i-1][j]
			dp[i][j] = useThisCoin + notUseThisCoin
		}
	}
	return dp[len(coins)][target]
}

func main() {
	n := 10
	fmt.Println(waysToChange2(n))
}
